package Classic150;

import LinkedList.ListNode;

public class 反转链表2 {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        /*
            迭代，双指针，头插法
         */
        /*ListNode dummyHead = new ListNode(-1, head);
        ListNode pre = dummyHead;
        for (int i = 1; i < left; i++) pre = pre.next;
        ListNode cur = pre.next;
        int count = right - left;
        for (int i = 0; i < count; i++) {
            ListNode next = cur.next;
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }
        return dummyHead.next;*/

        /*
            递归，https://leetcode.cn/problems/reverse-linked-list-ii/solutions/37247/bu-bu-chai-jie-ru-he-di-gui-di-fan-zhuan-lian-biao/
         */
        // base case
        if (left == 1) {
            return reverseN(head, right);
        }
        // 前进到反转的起点触发 base case
        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;
    }

    ListNode successor = null; // 后驱节点

    // 反转以 head 为起点的 n 个节点，返回新的头结点
    private ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            // 记录第 n + 1 个节点
            successor = head.next;
            return head;
        }
        // 以 head.next 为起点，需要反转前 n - 1 个节点
        ListNode last = reverseN(head.next, n - 1);
        head.next.next = head;
        // 让反转之后的 head 节点和后面的节点连起来
        head.next = successor;
        return last;
    }
}
